UVa/12322 - Handgun Shooting Sport/12322.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <bitset>
  14 #include <string>
  15 #include <cstdio>
  16 #include <vector>
  17 #include <cmath>
  18 #include <queue>
  19 #include <deque>
  20 #include <stack>
  21 #include <list>
  22 #include <map>
  23 #include <set>
  24
  25 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define D(x) cout << #x " is " << x << endl
  28
  29 typedef pair< double, double > interval;
  30
  31 const double eps = 1e-9;
  32
  33 const int MAXN = 1001;
  34
  35 interval intervals[MAXN];
  36 int B;
  37
  38 void delete_redundant() {
  39     bitset<MAXN> deleted;
  40     for (int i = 0; i < B; ++i) {
  41         for (int j = 0; j < B; ++j) {
  42             if (i == j) continue;
  43             // delete interval j if interval i is completely inside it
  44             if (intervals[j].first < intervals[i].first - eps and intervals[i].second + eps < intervals[j].second) {
  45                 deleted[j] = true;
  46             }
  47         }
  48     }
  49     int k = 0;
  50     for (int i = 0; i < B; ++i) {
  51         if (!deleted[i]) intervals[k++] = intervals[i];
  52     }
  53     B = k;
  54 }
  55
  56 int main(){
  57     while (cin >> B) {
  58         if (B == 0) break;
  59         for (int i = 0; i < B; ++i) {
  60             int x1, y1, x2, y2;
  61             cin >> x1 >> y1 >> x2 >> y2;
  62             double t1 = atan2(y1, x1), t2 = atan2(y2, x2);
  63             intervals[i] = make_pair( min(t1, t2), max(t1, t2) );
  64         }
  65         delete_redundant();
  66         sort(intervals, intervals + B);
  67         int ans = 0;
  68         for (int i = 0; i < B; ) {
  69             ans++;
  70             double pick = intervals[i].second;
  71             while (i < B and intervals[i].first - eps < pick) i++;
  72         }
  73         printf("%d\n", ans);
  74     }
  75     return 0;
  76 }